package com.example.leetcode.prcatice;

import java.util.*;

/**
 * 给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
 *
 * <p>例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
 * 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
 *
 * <p>求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2 解释：最优策略是先乘坐第一辆公交车到达车站 7 ,
 * 然后换乘第二辆公交车到车站 6
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bus-routes
 * 公交路线
 */
public class Test815 {

    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source == target) return 0;
        HashMap<Integer, List<Integer>> map = new HashMap<>(); // 记录<station,bus{}> 记录车站有哪些车经过
        for (int i =0 ;i<routes.length;i++){     //遍历所有的车站
            for (int s:routes[i]){
                if (!map.containsKey(s)){
                    int finalI = i;
                    map.put(s,new ArrayList<Integer>(){{add(finalI);}});
                }
                map.get(s).add(i);
            }
        }
        int[] record = new int[routes.length]; // 记录已经做过的公交
        Queue<Integer> queue = new LinkedList<>(); // 记录辐射的车站
        queue.offer(source);
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            count++;
            while (size-- >0){
                int cur = queue.poll(); // 取出
                for (int i:map.get(cur)){
                    if(record[i] ==1) continue;
                    record[i] =1;
                    for ( int s: routes[i]) {
                        if(s == target) return count;
                        if (s == cur) continue;
                        queue.offer(s);
                     }
                }
            }
        }
        return -1;
    }
}
